1.引言

谱聚类是一种在探索性数据分析中使用最为广泛的技术，其应用涉及到统计、计算科学、生物学、社会科学或者心理学。几乎每个科学领域在处理实验数据过程中，人们都尝试通过识别数据中具有“相似特征”的类别来获取该数据的第一印象。本文将为读者介绍谱聚类方法。相比于传统算法如k-means或者最短距离法(single linkage)，谱聚类具有很多基本的优点。通过谱聚类获得的结果通常要比传统聚类获得的结果要好，并且谱聚类非常易于实现，能够通过标准线性代数方法有效地求解。

本文主要介绍谱聚类方法。我们分析了关于谱聚类不同的观点和谱聚类的工作机制。除了基本的线性代数，读者不需要具有特定的数学背景。同时，由于关于谱聚类的文献数量太多，我们不再赘述关于谱聚类的所有文献。本文前两个部分主要是逐步介绍关于谱聚类所使用的数学对象：相似图在第二部分，图的拉普拉斯矩阵在第三部分。谱聚类算法的介绍在第四部分。接下来的三个部分将解释为什么这些算法有作用：第五部分描述了图的划分方法，第六部分是随机游走(random walk)的观点, 第七部分是扰动理论(perturbation theory)。在第八部分中，我们研究了一些与谱聚类相关的实际问题，第九部分讨论了一些谱聚类的扩展和关于谱聚类文献。

2.相似图

给一组数据点$x_1,…,x_n$,在每一对数据点$x_i$ 和 $x_j$之间定义相似度$s_{ij}$,聚类的直接目标是把数据点分为几个不同的类别，使得同一类别中数据点的相似度最大，不同类别中数据点的相似度最小。如果我们只知道数据点之间的相似度信息，一个表示这些数据点比较好的方法是相似图的形式(similarity graph)$G=(V,E)$。 相似图中每一个顶点$v_i$表示一个数据点$x_i$。如果两个顶点$x_i$和$x_j$之间的相似度$s_{ij}$为正并且大于某个确定的阈值，那么这两个顶点是以$s_{ij}$为权重的边连接的。现在，聚类问题可以重新定义为相似图问题：我们需要找到一个这样的分割，不同类别之间的边具有非常低的权重，而同一类别中的边具有比较高的权重(这意味着在同一类中的数据点是相似的)。为了能够形式化这样的表示，我们首先介绍一些图的基本定义，简要讨论一下我们将要研究的图的种类。

2.1 图的定义

$G=(V,E)$是一个无向图，顶点集为$V={v_1,…,v_n}$. 下面我们假定图$G$是有权的，也就是说每两个顶点$v_i$和$v_j$有一个非负的权重$w_{ij}>=0$。图的加权邻接矩阵是$W=(w_{ij}). i,j=1,…,n$。如果$w_{ij}=0$意味着顶点$v_i$和$v_j$之间没有边连接。因为$G$是无向图，我们令$w_{ij}=w_{ji}$。顶点$v_i \in V$的度定义如下：

$$d_i=\sum^{n}_{j=1}w_{ij}.$$

请注意，事实上，上式只计算了与$v_i$邻接的所有顶点，其他顶点的权重都为0。度矩阵$D$是对角矩阵，其对角线上的度为$d_i,…,d_n$。给定一个顶点子集$A \subset B$，我们用